package algotithm.leetcode.dp.hot.test416;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/12-22:18
 * @URL https://leetcode-cn.com/problems/partition-equal-subset-sum/
 * @Title 416. 分割等和子集
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,5,11,5};
        boolean b = solution.canPartition(nums);
        System.out.println(b);
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        if (nums.length < 2) {
            return false;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        if ((sum % 2) != 0) {
            return false;
        }
        int target = sum / 2;
        if (max > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = target; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}
